{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "b3b8a73f",
   "metadata": {},
   "source": [
    "## 2.2 快速查找数组中给定次序的元素\n",
    "\n",
    "1. 将数组分为三部分\n",
    "2. 设计随机元素查找算法\n",
    "3. 递归选择"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "ab048f37",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "median number is :26\n",
      "The element selected is 165\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "\n",
    "def arrange_array_by_pivot(array, pivot):\n",
    "    \"\"\" 将数组分为3部分， 第1部分元素小于pivot, 第二部分元素等于pivot，第三部分元素大于pivot \"\"\"\n",
    "    i = 0\n",
    "    j = len(array) - 1\n",
    "\n",
    "    while i < j:\n",
    "        if array[i] < pivot:\n",
    "            i += 1\n",
    "        elif array[i] >= pivot:\n",
    "            temp = array[j]\n",
    "            array[j] = array[i]\n",
    "            array[i] = temp\n",
    "            j -= 1\n",
    "        \n",
    "    if array[i] < pivot:\n",
    "        i += 1\n",
    "    \n",
    "    k = i\n",
    "    S1 = array[0:i]\n",
    "    j = len(array) - 1\n",
    "\n",
    "    while i < j:\n",
    "        if array[i] == pivot:\n",
    "            i += 1\n",
    "        else:\n",
    "            temp = array[j]\n",
    "            array[j] = array[i]\n",
    "            array[i] = temp\n",
    "            j -= 1\n",
    "        \n",
    "    if array[i] == pivot:\n",
    "        i += 1\n",
    "    \n",
    "    S2 = array[k:i]\n",
    "    S3 = array[i:]\n",
    "\n",
    "    return S1, S2, S3\n",
    "    \n",
    "\n",
    "def selection(array, k):\n",
    "    \"\"\" 查找数组中第k小的元素 \"\"\"\n",
    "    if len(array) <= 1:\n",
    "        return array[0]\n",
    "    if k > len(array):\n",
    "        raise Exception('Out of range!')\n",
    "    \n",
    "    pivot = array[0]\n",
    "    is_good_pivot = False\n",
    "\n",
    "    while is_good_pivot != True:\n",
    "        pivot = random.choice(array)\n",
    "\n",
    "        S1, S2, S3 = arrange_array_by_pivot(array, pivot)\n",
    "        if len(S1) <= int((3/4)*len(array)) and len(S3) <= int((3/4)*len(array)):\n",
    "            is_good_pivot = True\n",
    "    \n",
    "    if len(S1) > 0 and k <= len(S1):\n",
    "        return selection(S1, k)\n",
    "    elif len(S2) > 0 and k <= len(S1) + len(S2):\n",
    "        return pivot\n",
    "    else:\n",
    "        return selection(S3, k - len(S1) - len(S2))\n",
    "    raise Exception('error')\n",
    "\n",
    "array = [138, 132, 119, 149, 116, 124, 121, 144, 203, 105, 180, 185, 165,\n",
    "         113, 173, 117, 176, 196, 122, 142, 172, 162, 190, 118, 150, 128, 186, 177, 189, 183,\n",
    "         189, 123, 190, 133, 147, 182, 170, 183, 157, 124, 194, 115, 203, 203, 200, 152, 178,\n",
    "         186, 118, 183, 202]\n",
    "\n",
    "k = int((len(array) + 1) / 2)\n",
    "print(f\"median number is :{k}\")\n",
    "median = selection(array, k)\n",
    "print('The element selected is', median)\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "env_py38",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.18"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
